package com.tgy.排序;

import java.util.Arrays;

/***
 * @ClassName: BubbleSort
 * @Description: 冒泡排序
 * @Auther: tanggy3
 * @Date: 16:50 2022/8/11
 * @version : V1.0
 */
public class BubbleSort {
    public static void main(String[] args) {
        int arr[] = {3, 9, -1, 10, -2};

        int arr2[] = {-2, -1, 3, 9, 10};
        int[] intArr = Utils.getIntArr();
        //detail(intArr);
        //oneDeal(intArr);//11587
        fianlDeal(intArr);//9468ms，大循环进行了79391次

        //System.out.println(Arrays.toString(detail(intArr)));
        //System.out.println(Arrays.toString(fianlDeal(intArr)));
    }

    /**
     * 展示细节
     *
     * @param arr
     * @return
     */
    public static int[] detail(int[] arr) {
        long l = System.currentTimeMillis();
        //第一趟排序，把最大的放在最后
        for (int i = 0; i < arr.length - 1; i++) {
            if (arr[i] > arr[i + 1]) {
                int temp = arr[i];
                arr[i] = arr[i + 1];
                arr[i + 1] = temp;
            }
        }
        System.out.println("第一次排序后");
        System.out.println(Arrays.toString(arr));

        for (int i = 0; i < arr.length - 1 - 1; i++) {
            if (arr[i] > arr[i + 1]) {
                int temp = arr[i];
                arr[i] = arr[i + 1];
                arr[i + 1] = temp;
            }
        }
        System.out.println("第二次排序后");
        System.out.println(Arrays.toString(arr));

        for (int i = 0; i < arr.length - 1 - 1 - 1; i++) {
            if (arr[i] > arr[i + 1]) {
                int temp = arr[i];
                arr[i] = arr[i + 1];
                arr[i + 1] = temp;
            }
        }
        System.out.println("第三次排序后");
        System.out.println(Arrays.toString(arr));


        for (int i = 0; i < arr.length - 1 - 1 - 1 - 1; i++) {
            if (arr[i] > arr[i + 1]) {
                int temp = arr[i];
                arr[i] = arr[i + 1];
                arr[i + 1] = temp;
            }
        }
        System.out.println("第四次排序后");
        System.out.println(Arrays.toString(arr));
        long l1 = System.currentTimeMillis() - l;
        System.out.println("耗时"+l1+"ms");
        return arr;
    }

    /**
     * 一次处理完毕
     *
     * @param arr
     * @return
     */
    public static int[] oneDeal(int[] arr) {
        long l = System.currentTimeMillis();
        for (int j = 0; j < arr.length - 1; j++) {
            for (int i = 0; i < arr.length - 1; i++) {
                if (arr[i] > arr[i + 1]) {
                    int temp = arr[i];
                    arr[i] = arr[i + 1];
                    arr[i + 1] = temp;
                }
            }
        }
        long l1 = System.currentTimeMillis() - l;
        System.out.println("耗时"+l1+"ms");
        return arr;
    }


    /**
     * 最终优化
     *
     * @param arr
     * @return
     */
    public static int[] fianlDeal(int[] arr) {
        long l = System.currentTimeMillis();
        int length = arr.length-1;
        out:for (int i = 0; i < length; i++) {
            //定义一个标志，如果有一次小循环没有进入if语句，就直接推出大循环，表示已经有顺序
            boolean flag = true;
            for (int k = 0; k <length-i ; k++) {
                if (arr[k] > arr[k + 1]) {
                    int temp = arr[k];
                    arr[k] = arr[k + 1];
                    arr[k + 1] = temp;
                    flag = false;
                }
            }
            if (flag) {
                System.out.println("已经排序完毕，提前退出,大循环进行了"+i+"次");
                break out;
            }
        }
        long l1 = System.currentTimeMillis() - l;
        System.out.println("耗时"+l1+"ms");
        return arr;
    }
}
